package com.universe.arithmetic.baseSort;

import com.universe.util.ArrayUtil;

/**
 * @Author：ghostbamboo
 * @Description： 归并排序
 * @Theory： 归并排序问题：当归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法
 * 采用经典的分治（divide-and-conquer） 策略（分治法将问题分(divide)成一些小的问题然后递归
 * 求解，而治(conquer)的阶段则将分的阶段得到的各答案"修 补"在一起，即分而治之)。
 * 平均时间复杂度 O（n * log n） 空间复杂度 O（n）
 * @Date： 17:41 2019/12/20
 */
public class MergeSort {

    public static void mergeSort(int left, int right, int[] arr, int[] temp) {
        if (left < right) {
            int mid = (left + right) / 2;

            //向左递归分解
            mergeSort(left, mid, arr, temp);
            //向右递归分解
            mergeSort(mid + 1, right, arr, temp);

            merge(left, mid, right, arr, temp);
        }

    }

    private static void merge(int left, int mid, int right, int[] arr, int[] temp) {
        int i = left; //左边数组指针
        int j = mid + 1; //右边数组指针
        int index = 0; //临时数组指针

        //--------------------------------  1  ------------------------------//
        while (i <= mid && j <= right) {
            //左边大于等于右边
            if (arr[i] >= arr[j]) {
                temp[index] = arr[j];
                j++;
                index++;
            } else {    //左边小于右边
                temp[index] = arr[i];
                i++;
                index++;
            }
        }
        //--------------------------------  2  ------------------------------//
        //填充左边剩下的数
        while (i <= mid) {
            temp[index] = arr[i];
            i++;
            index++;
        }
        //填充右边剩下的数
        while (j <= right) {
            temp[index] = arr[j];
            j++;
            index++;
        }
        //--------------------------------  3  ------------------------------//
        //替换temp数组的有序数据到原数组
        index = 0;
        int tempLeft = left;
        while (tempLeft <= right) {
            arr[tempLeft] = temp[index];
            index++;
            tempLeft++;
        }

    }


    public static void main(String[] args) {
        System.out.println("单数组测试………………");
        int[] arr = {-9, 78, 0, 23, -567, 70, -1, 900, 4561};
        int[] temp = new int[arr.length];
        int[] copy = ArrayUtil.copyArray(arr);

        mergeSort(0, arr.length - 1, arr, temp);
        ArrayUtil.systemSort(copy);
        boolean success = ArrayUtil.isEqual(arr, copy);
        System.out.println(success ? "Nice! 排序成功" : "What a pity! Failed!!!");
        for (int i : arr) {
            System.out.print(i + " ");
        }

        //多数组测试
        System.out.println("\n多数组测试………………");
        for (int i = 0; i < 1000; i++) {
            int[] arr1 = ArrayUtil.generateArray(100, 9999);
            int arrTemp[] = new int[arr1.length];
            int[] arr2 = ArrayUtil.copyArray(arr1);

            mergeSort(0, arr1.length - 1, arr1, arrTemp);
            ArrayUtil.systemSort(arr2);
            boolean b = ArrayUtil.isEqual(arr, copy);
            if (!b) {
                throw new RuntimeException("排序失败");
            }
        }
        System.out.println("排序成功！");

    }
}
